package 中等;

/*
* 奇偶链表
* 力扣地址：https://leetcode-cn.com/problems/odd-even-linked-list/
* 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
* 请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
* 示例 1:
* 输入: 1->2->3->4->5->NULL
* 输出: 1->3->5->2->4->NULL
* 示例 2:
* 输入: 2->1->3->5->6->4->7->NULL
* 输出: 2->3->6->7->1->5->4->NULL
* 思路：将链表一分为2，一个存放偶，一个存放奇，最后将偶和奇连接
* */

public class demo328 {

    public static void main(String[] args) {

    }

    //第一版
    public static ListNode oddEvenList(ListNode head) {
        if (head == null)
            return head;
        if (head.next == null)
            return head;
        if (head.next.next == null)
            return head;

        ListNode lnode = head;
        ListNode jnode = head;
        ListNode rnode = head.next;
        ListNode tnode = rnode;

        int len = 0;
        while (lnode.next != null)
        {
            len++;
            lnode = lnode.next;
        }

        int i = 0;
        while (i < len/2)
        {
            jnode.next = jnode.next.next;
            rnode.next = rnode.next.next;
            jnode = jnode.next;
            rnode = rnode.next;
            i++;
        }

        jnode.next = tnode;

        return head;
    }

    public class ListNode {
      int val;
      ListNode next;
      ListNode() {}

      ListNode(int val)
      {
          this.val = val;
      }

      ListNode(int val, ListNode next)
      {
          this.val = val;
          this.next = next;
      }
  }
}
